
import java.io.*;
import java.util.*;

public class Main {

   // Variáveis globais
   public static int pages = 0;
   
   // teste
   public static ArrayList<Node> arvore = new ArrayList<Node> ();

	// Função utilizada apenas para resumir a leitura
   public static String ler(BufferedReader linha) {
		String retorno = new String();
		try {
			retorno = linha.readLine();
		}
		catch (IOException e) {
			System.out.println("Erro: "+e);
		}

		return retorno;
	}

   // Essa função insere um registro em uma página que não estiver cheia
   public static Node inserirRegistro(Node tree, String reg, ArrayList<Node> arvore) {
      try {
         // Abre a página correta onde o registro precisa ser inserido

         // DEBUG
         /*
         System.out.println("registro = "+reg);
         */

         String[] registro = reg.split(" ");
         String[] regs = null;
         String aux;
         int i;
         int valor = new Integer(registro[1]).intValue();
         int unidades = new Integer(registro[2]).intValue();

         Node node = buscarNo(tree, valor, unidades);
         File page = null;
         if (tree == null) page = new File("pages/page0");
         else page = new File("pages/"+(node.getPage(valor, unidades)));

         BufferedWriter writer = new BufferedWriter(new FileWriter(page, true));
         BufferedReader reader = new BufferedReader(new FileReader(page));

         // Verifica se a página está cheia
         String qtde = reader.readLine();
         if (qtde == null) {
            writer.write("1");
         }
         else if ((new Integer(qtde).intValue()) > 3) {
            // Verificar a divisão de págs

            int cmp;
            if (node != null) {
               if (node.getCmp() == 0) cmp = 1;
               else cmp = 0;
            }
            else cmp = 0;
            TreeMap<Integer,String> listaRegs = new TreeMap<Integer,String> ();

            aux = reader.readLine();
            if (cmp == 0) {
               while (aux != null) {
                  listaRegs.put( new Integer(aux.split(" ")[1]), aux );
                  aux = reader.readLine();
               }
               listaRegs.put( new Integer(reg.split(" ")[1]), reg );
            }
            else {
               while (aux != null) {
                  listaRegs.put( new Integer(aux.split(" ")[2]), aux );
                  aux = reader.readLine();
               }
               listaRegs.put( new Integer(reg.split(" ")[2]), reg );
            }
            // Escreve os registros nas duas págs
            Object[] keys = listaRegs.keySet().toArray();

            writer.close();
            writer = new BufferedWriter(new FileWriter(page));
            String page1 = page.getName();
            writer.write("3");
            for (i=0; i<=2; i++) {
               writer.newLine();
               writer.write(listaRegs.get(keys[i]));
            }
            writer.close();
            pages++;
            File newpage = new File("pages/page"+ (new Integer(pages).toString()));
            writer = new BufferedWriter(new FileWriter(newpage, true));
            String page2 = newpage.getName();
            writer.write("2");

            // DEBUG
            /*
            for (i=0; i<listaRegs.size(); i++) System.out.println(keys[i]);
            System.out.println("page1 = "+page1);
            System.out.println("page2 = "+page2);
            */

            for (i=3; i<=4; i++) {
               writer.newLine();
               writer.write(listaRegs.get(keys[i]));
            }
            writer.close();

            // Cria o novo nó
            valor = new Integer(listaRegs.get(keys[2]).split(" ")[1]).intValue();
            unidades = new Integer(listaRegs.get(keys[2]).split(" ")[2]).intValue();

            Node newNode = new Node(valor, unidades, cmp, page1, page2);
            if (node == null) {
               tree = newNode;
            }
            else {
               node.setChildren(page1, newNode);
            }

            arvore.add(newNode);
            return tree;
         }

         else {
            int novaqtde = new Integer(qtde).intValue();
            i = 0;
            regs = new String [novaqtde];
            novaqtde++;
            qtde = Integer.toString(novaqtde);

            // Recria o arquivo, atualizando a qtde de registros
            aux = reader.readLine();
            while (aux != null) {
               regs[i] = aux;
               aux = reader.readLine();
               i++;
            }
            writer.close();
            writer = new BufferedWriter(new FileWriter(page));
            writer.write(qtde, 0, 1);
            for (int j=0; j < i; j++) {
               writer.newLine();
               writer.write(regs[j]);
            }

         }

         // Insere o novo registro
         writer.newLine();
         writer.write(reg);
         writer.flush();
         writer.close();

      }
      catch (IOException e){
         System.out.println(e);
      }

      return tree;
   }

   // Essa função retorna o nó que aponta para a pág. onde o registro deve ser inserido
   public static Node buscarNo(Node tree, int valor, int unidades) {
      boolean achou = false;
      if (tree == null) {
         return tree;
      }
      else {
         Node node = tree;
         Node n = node;
         Node prox = null;
         while (node != null) {
            if (node.getCmp() == 0) {
               if (valor <= node.getValor()) prox = node.getNodeLeft();
               else prox = node.getNodeRight();
            }
            else {
               if (unidades <= node.getNumeroUnidades()) prox = node.getNodeLeft();
               else prox = node.getNodeRight();
            }

            n = node;
            node = prox;
         }

         return n;
      }
   }

   public static void buscaPorIntervalo(Node tree, String query) {
      int vmin, vmax, nmin, nmax, i, valor, un, n;
      String[] q = query.split(" ");
      ArrayList<Node> nodes = new ArrayList<Node>(), nodes2 = null;
      ArrayList<String> pages = new ArrayList<String>();
      boolean esq = false, dir = false;
      String reg;

      // Resultado da busca ordenado por ID's
      TreeMap<Integer,String> resultado = new TreeMap<Integer,String>();

      // Arrumando os valores da busca
      if (q[0].equals("_")) vmin = 0;
      else vmin = (new Integer(q[0])).intValue();

      if (q[1].equals("_")) vmax = Integer.MAX_VALUE;
      else vmax = (new Integer(q[1])).intValue();
	
      if (q[3].equals("_")) nmin = 0;
      else nmin = (new Integer(q[3])).intValue();

      if (q[4].equals("_")) nmax = Integer.MAX_VALUE;
      else nmax = (new Integer(q[4])).intValue();
      
      // Fazendo a busca
      if (tree != null) {
         nodes.add(tree);

         // Busca AND
         if (q[2].equals("&")) {
            while (nodes.size() > 0) {
               for (i=0; i < nodes.size(); i++) {
                  Node aux = nodes.get(i);
                  esq = false; dir = false;
                  if (aux.getCmp() == 0) {
                     if (aux.getValor() < vmin) dir = true;
                     else if (aux.getValor() > vmax) esq = true;
                     else { dir = true; esq = true; }
                  }
                  else {
                     if (aux.getNumeroUnidades() < nmin) dir = true;
                     else if (aux.getNumeroUnidades() > nmax) esq = true;
                     else { dir = true; esq = true; }
                  }

                  nodes2 = new ArrayList<Node>();
                  
                  if (dir) {
                     if (aux.getNodeRight() != null) nodes2.add(aux.getNodeRight());
                     else pages.add(aux.getPageRight());
                  }
                  if (esq) {
                     if (aux.getNodeLeft() != null) nodes2.add(aux.getNodeLeft());
                     else pages.add(aux.getPageLeft());
                  }
               }

               nodes = nodes2;
            }

            // Acessa as págs ordenando os registros corretos
            for (i=0; i < pages.size(); i++) {
               try {
                  BufferedReader reader = new BufferedReader(new FileReader("pages/"+pages.get(i)));
                  reg = reader.readLine();
                  if (! reg.equals("0")) {
                     reg = reader.readLine();
                     while (reg != null) {
                        valor = (new Integer(reg.split(" ")[1])).intValue();
                        un = (new Integer(reg.split(" ")[2])).intValue();
                        if ((valor >= vmin) && (valor <= vmax) && (un >= nmin) && (un <= nmax)) {
                           resultado.put(new Integer(reg.split(" ")[0]), reg);
                        }
                        reg = reader.readLine();
                     }
                  }
               }
               catch (IOException e){}
            }
         }

         else {
            // busca OR
         }

         // Imprime o resultado da busca:
         Object[] keys = resultado.keySet().toArray();
         for (i=0; i < resultado.size(); i++) System.out.println(resultado.get(keys[i]));
      }
}


   // MAIN
   public static void main(String[] args) {
      // Variáveis

		BufferedReader linha = new BufferedReader(new InputStreamReader(System.in));
      String str;
      Node tree = null;
      FileReader reader = null;
      FileWriter writer = null;
      int regs, depth = 0, i;

      regs = new Integer(ler(linha)).intValue();

      for (i=1; i<=regs; i++) {
         // Aqui é construída a árvore
         str = ler(linha);

         tree = inserirRegistro(tree, str, arvore);
      }



      // DEBUG
      /*
      for(i=0; i<=arvore.size()-1; i++) {
         System.out.println("Node: ["+arvore.get(i).valor+", "+arvore.get(i).numeroUnidades+"]");
         System.out.println("Filhos: "+arvore.get(i).filhoEsq+", "+arvore.get(i).filhoDir);
         System.out.println("Paginas: "+arvore.get(i).pageLeft+", "+arvore.get(i).pageRight);
         System.out.println("CMP: "+arvore.get(i).cmp);
         System.out.println("-------------------------------");
      }
      */

      // Pega a string da busca e trata
      str = ler(linha);

      buscaPorIntervalo(tree, str);
   }
}

